A structure-based virtual screening (SBVS) was conducted on a ligand-supported homology model of the human histamine H4 receptor (hH4R). More than 8.7 million 3D structures derived from different vendor databases were investigated by docking to the hH4R binding site using FlexX. A total of 255 selected compounds were tested by radioligand binding assay and 16 of them possessed significant [(3)H]histamine displacement. Several novel scaffolds were identified that can be used to develop selective H4 ligands in the future. As far as we know, this is the first SBVS reported on H4R, representing one of the largest virtual screens validated by the biological evaluation of the virtual hits.